package com.hyb.algorithm.data.struct.dp;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: ybhu
 * @create: 2021/08/31 00:00
 *
 * 452. 用最少数量的箭引爆气球
 *
 * https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/
 */
public class FindMinArrowShots {

    public static void main(String[] args) {

        int[][] points=new int[][]{{-2147483646,-2147483645},{2147483646,2147483647}};
        FindMinArrowShots exe=new FindMinArrowShots();
        exe.findMinArrowShots(points);
    }


    public int findMinArrowShots(int[][] points) {
        if(points.length<=0){
            return 0;
        }

        Arrays.sort(points,new Comparator<int[]>(){
            @Override
            public int compare(int[] a,int[] b){
                return a[1]-b[1];
            }
        });

        int count=1;
        int currentEnd=points[0][1];

        for(int[] point:points){
            if(currentEnd<point[0]){
                count++;
                currentEnd=point[1];
            }
        }

        return count;
    }
}
